package 递归.二分查找;

import 递归.快排.QuickSort;

public class BinarySearch {
    private BinarySearch(){};
    private static  int search(int[] data, int target){
        return search(data, 0, data.length - 1, target);
    }
    private static int search(int[] data, int l, int r, int target){
        if (l > r) return -1;
        int mid = (l+r) / 2;
        if (data[mid] - (target) == 0){
            return mid;
        }else if(data[mid] - (target) < 0){
            return search(data, mid+1, r, target);
        }else {
            return search(data, l, mid - 1, target);
        }
    }
    /*返回比target大的最小元素索引 [l, r]*/
    public static int upper(int []data, int target){
        int mid = 0;
        int l = 0;
        /*右侧扩大1*/
        int r = data.length;
        while (l < r){
            mid = (l+r) / 2;
            if (target >= data[mid]){
                l = mid+1;
            }else {
                r = mid;
            }
        }
        return l;
    }
    /*如果存在，则返回最大索引（<=target的最大索引）
    * 不存在则返回upper*/
    public static int ceil(int []data, int target){
        int upper = upper(data, target);
        if (upper -1 >= 0 && data[upper - 1] == target){
            return upper - 1;
        }else return upper;
    }
    /*返回target的最小索引
    * 否则返回upper*/
    public static int lower_ceil(int []data, int target){
        int mid = 0;
        int l = 0;
        /*右侧扩大1*/
        int r = data.length;
        while (l < r){
            mid = (l+r) / 2;
            /*比upper少了=*/
            if (target > data[mid]){
                l = mid+1;
            }else {
                r = mid;
            }
        }
        return l;
    }
    /*返回<target的最大索引*/
    /*死循环*/
    public static int lower(int []data, int target){
        int mid = 0;
        int l = -1;
        int r = data.length - 1;
        while (l < r){
            /*改变mid公式*/
            mid = l + (r - l + 1)/2;
            if (target > data[mid]){
                l = mid;
            }else {
                r = mid - 1;
            }
        }
        return l;
    }
    /*返回target的最小索引,否则返回Lower*/
    public static int lower_floor(int []data, int target){
       if(lower(data, target) + 1 < data.length&&
        data[lower(data, target) + 1] == target
               ){
           return lower(data, target) + 1;
       }else return lower(data, target);
    }
    /*返回<=target的最大索引*/
    public static int upper_floor(int []data, int target){
        int mid = 0;
        int l = -1;
        /*右侧扩大1*/
        int r = data.length - 1;
        while (l < r){
            mid = l + (r - l + 1)/2;
            if (target >= data[mid]){
                l = mid ;
            }else {
                r = mid - 1;
            }
        }
        return l;
    }
    public static void main(String[] args) {
        int[] a = {1,2,3,4,4,5,5,7};
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i] + " " + BinarySearch.upper_floor(a, a[i]));
        }
        System.out.println(BinarySearch.upper_floor(a, 0));
        System.out.println(BinarySearch.upper_floor(a, 9));

    }
}
